#include<stdio.h>
#include<time.h>
#include<stdlib.h>

/* 暴力破解，三重循环 T(N) = O(N^3) */
int MaxSubseqSum1(int arr[], int N)
{
    int ThisSum, MaxSum=0;
    int i, j, k;
    for (i = 0; i < N; i++) {
        for (j = i; j < N; j++) {
            ThisSum = 0;
            for (k = i; k <= j; k++)
                ThisSum += arr[k];
            if (ThisSum > MaxSum)
                MaxSum = ThisSum;
        }
    }

    return MaxSum;
}


/* 降为两重循环 T(N) = O(N^2) */
int MaxSubseqSum2(int arr[], int N)
{
    int ThisSum, MaxSum=0;
    int i, j;
    for (i = 0; i < N; i++) {
        ThisSum = 0;
        for (j = i; j < N; j++) {
            ThisSum += arr[j];
            if (ThisSum > MaxSum)
                MaxSum = ThisSum;
        }
    }
    
    return MaxSum;
}


/* 分而治之 T(N) = O(NlogN) */
// 返回三个数的最大数
int Max3(int A, int B, int C)
{
    return A > B ? A > C ? A : C : B > C ? B : C;
}

// 分治法求最大子列和
int DivideAndConquer(int List[], int left, int right)
{
    int MaxLeftSum, MaxRightSum; // 存放左右子列的解
    int MaxLeftBorderSum, MaxRightBorderSum; //存放跨分界线的结果

    int LeftBorderSum, RightBorderSum;
    int center, i;

    // 递归的终止条件，子列只有一个数字
    if (left == right) {
        if (List[left] > 0) return List[left];
        else return 0;
    }

    // 下面是“分”的过程
    center = (left + right) / 2;
    // 递归求得两边最大子列和
    MaxLeftSum = DivideAndConquer(List, left, center);
    MaxRightSum = DivideAndConquer(List, center+1, right);

    // 下面求跨分界线的最大子列和
    MaxLeftBorderSum = 0; LeftBorderSum = 0;
    for (i = center; i >= left; i--) { // 从中线向左扫描
        LeftBorderSum += List[i];
        if (LeftBorderSum > MaxLeftBorderSum)
            MaxLeftBorderSum = LeftBorderSum;
    } // 左边扫描结束
    MaxRightBorderSum = 0; RightBorderSum = 0;
    for (i = center + 1; i <= right; i++) { // 从中线向右扫描
        RightBorderSum += List[i];
        if (RightBorderSum > MaxRightBorderSum)
            MaxRightBorderSum = RightBorderSum;
    } // 右边扫描结束

    // 下面返回“治”的结果
    return Max3(MaxLeftSum, MaxRightSum, MaxLeftBorderSum \
            + MaxRightBorderSum);
}

int MaxSubseqSum3(int List[], int N)
{
    return DivideAndConquer(List, 0, N-1);
}


/* 在线算法 T(N) = O(N) */
int MaxSubseqSum4(int List[], int N)
{
    int ThisSum=0, MaxSum=0;
    int i;
    for (i = 0; i < N; i++) {
        ThisSum += List[i];
        if (ThisSum > MaxSum)
            MaxSum = ThisSum;
        else if (ThisSum < 0)
            ThisSum = 0;
    }

    return MaxSum;
}



clock_t start, stop;
double duration;

int main ()
{
    int N;
    scanf("%d", &N);
    int List[N];
    int i;
    srand((unsigned)(time(NULL)));
    for (i = 0; i < N; i++)
        List[i] =(int)((rand() / (RAND_MAX + 1.0)) * 20 - 10);
    int maxsum;

    // 算法1
    printf("MaxSubseqSum1 ...\n");
    start = clock();
    maxsum = MaxSubseqSum1(List, N);
    stop = clock();
    duration = ((double)(stop - start)) / CLOCKS_PER_SEC;

    printf("The max subsequence sum is %d.\n", maxsum);
    printf("Elapsed CPU time is %f.\n", duration);
    printf("\n\n=============================================\n");

    // 算法2
    printf("MaxSubseqSum2 ...\n");
    start = clock();
    maxsum = MaxSubseqSum2(List, N);
    stop = clock();
    duration = ((double)(stop - start)) / CLOCKS_PER_SEC;

    printf("The max subsequence sum is %d.\n", maxsum);
    printf("Elapsed CPU time is %f.\n", duration);
    printf("\n\n=============================================\n");
    
    // 算法3
    printf("MaxSubseqSum3 ...\n");
    start = clock();
    maxsum = MaxSubseqSum3(List, N);
    stop = clock();
    duration = ((double)(stop - start)) / CLOCKS_PER_SEC;

    printf("The max subsequence sum is %d.\n", maxsum);
    printf("Elapsed CPU time is %f.\n", duration);
    printf("\n\n=============================================\n");

    // 算法4
    printf("MaxSubseqSum4 ...\n");
    start = clock();
    maxsum = MaxSubseqSum4(List, N);
    stop = clock();
    duration = ((double)(stop - start)) / CLOCKS_PER_SEC;

    printf("The max subsequence sum is %d.\n", maxsum);
    printf("Elapsed CPU time is %f.\n", duration);
    printf("\n\n=============================================\n");
}
